#ifndef TACORES_DEPTHFIRSTSEARCH_H
#define TACORES_DEPTHFIRSTSEARCH_H

using namespace std;

#include "Graph.h"
#include <vector>

// O(V + E)
class DepthFirstSearch
{
public:
	DepthFirstSearch(Graph& g)
		: g (g)
	{
	}

	void search(int s)
	{
		initialize();
		visit(s);

		int size = g.numVertices();
		for(int i = 0; i < size; ++i)
		{
			if(color[i] == White)
			{
				visit(i);
			}
		}
	}

	vector<int> getPredecessor() { return pred; }
	vector<int> getDiscovered() { return d; }
	vector<int> getFinished() { return f; }

private:
	void initialize()
	{
		int size = g.numVertices();
		d.assign(size, -1);
		f.assign(size, -1);
		pred.assign(size, -1);
		color.assign(size, White);
		counter = 0;
	}

	void visit(int u)
	{
		color[u] = Gray;
		d[u] = ++counter;

		VertexList::const_iterator end = g.end(u);
		for(VertexList::const_iterator it = g.begin(u); it != end; ++it)
		{
			int v = it->first;
			if(color[v] == White)
			{
				pred[v] = u;
				visit(v);
			}
		}
		color[u] = Black;
		f[u] = ++counter;
	}

	Graph& g;
	vector<int> d;
	vector<int> f;
	vector<int> pred;
	vector<vertexColor> color;
	int counter;
};
typedef DepthFirstSearch DFS;

#endif

